//
// Created by mac on 2023/10/29.
//

// 最长重复子数组
class Solution
{
public:
    int findLength(vector<int>& nums1, vector<int>& nums2)
    {
        // 1、建表 && 初始化
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // 2、填表
        int ret = INT_MIN;
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j)
            {
                dp[i][j] = nums1[i - 1] == nums2[j - 1] ? dp[i - 1][j - 1] + 1 : 0;
                ret = max(ret, dp[i][j]);
            }

        // 3、返回值
        return ret;
    }
};

// 两个字符串的最小ASCII删除和
class Solution
{
public:
    int minimumDeleteSum(string s1, string s2)
    {
        // 1、建表
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // 2、初始化
        s1 = ' ' + s1;
        s2 = ' ' + s2;
        // 3、填表
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j)
            {
                int x1 = (s1[i] == s2[j] ? dp[i-1][j-1] + s1[i] : 0);
                int x2 = dp[i][j - 1];
                int x3 = dp[i - 1][j];
                dp[i][j] = max(max(x2, x3), x1);
            }
        // 4、返回值
        int sum = 0;
        for(int i = 1; i <= m; ++i) sum += s1[i];
        for(int j = 1; j <= n; ++j) sum += s2[j];
        return sum - 2 * dp[m][n];
    }
};

// 交错字符串
class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        // 1、建表
        int m = s1.size(), n = s2.size();
        if(m + n != s3.size()) return false;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));

        // 2、初始化
        s1 = ' ' + s1;
        s2 = ' ' + s2;
        s3 = ' ' + s3;

        dp[0][0] = true;
        for(int i = 1; i <= m; ++i) // 初始化第一行
            if(s1[i] == s3[i]) dp[i][0] = true;
            else break;
        for(int j = 1; j <= n; ++j) // 初始化第一列
            if(s2[j] == s3[j]) dp[0][j] = true;
            else break;

        // 3、填表
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j)
                dp[i][j] = (s1[i] == s3[i+j] && dp[i-1][j])
                           ||(s2[j] == s3[i+j] && dp[i][j-1]);

        // 4、返回值
        return dp[m][n];
    }
};
/*
- 时间复杂度：O(mn)
- 空间复杂度：O(mn)
*/

